﻿using System;
using System;
using System.Collections.Generic;
using System.Collections.Generic;
using System.Linq;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using NetTopologySuite.Triangulate;
using OpenCvSharp.Internal.Vectors;

namespace PointAsLine.NotUsed
{
    public class PolygonBuilder2
    {
        public List<Polyline> BuildPolygonsFromSegmentsMain(List<Polyline> inputSegments, double epsilon = 2)
        {
            List < Polyline > allRes=new List<Polyline>();

            bool[] hasAdded = new bool[inputSegments.Count];
            while (true)
            {
                List<Polyline> subgroupPolylines = new List<Polyline>();
                for(var i = 0; i < inputSegments.Count; i++)
                {
                    if (hasAdded[i] == false)
                    {
                        subgroupPolylines.Add(inputSegments[i]);
                        hasAdded[i] = true;
                        break;
                    }
                }
                if(subgroupPolylines.Count == 0)
                {
                    break;
                }
                
                for (var i = 0; i < inputSegments.Count; i++)
                {
                    if (hasAdded[i] == false && inputSegments[i].GroupIndex == subgroupPolylines[0].GroupIndex)
                    {
                        subgroupPolylines.Add(inputSegments[i]);
                        hasAdded[i]= true;
                    }
                }
                var rs1 = BuildPolygonsOfSubgroup(subgroupPolylines, epsilon);
                allRes.AddRange(rs1);
            }
            
            var ts= FilterPolygons(allRes);
            ts = RemoveLenthSmall.Remove(ts, PointFFunc.MeterToPixel(50));

            RemoveUsedSegment(inputSegments, ts);

            return ts;
        }

        public List<Polyline> FilterPolygons(List<Polyline> allRes)
        {
            for (var i = allRes.Count - 1; i >= 0; i--)
            {
                var area = allRes[i].ComputeArea();
                if (area < 250 && allRes[i].Count < 6)
                {
                    allRes.RemoveAt(i);
                }
                else
                {
                    allRes[i].IsFinallyPolygon = true;
                }
            }
            allRes.Sort(new PolylineComparerByArea());
            bool[] removed=new bool[allRes.Count];
            for(var i = 0; i < allRes.Count; i++)
            {
                if (removed[i]) continue; ;
                for(var j=i+1; j < allRes.Count; j++)
                {
                    if (removed[j] == false)
                    {
                        if (PolygonContainmentChecker.IsPolygonContained(allRes[i], allRes[j], 0.95))
                        {
                            removed[j] = true;
                        }
                    }
                }
            }

            for(var i=allRes.Count - 1; i >= 0; i--)
            {
                if (removed[i]) { allRes.RemoveAt(i); }
            }

            return allRes;
        }

        private List<Polyline> BuildPolygonsOfSubgroup(List<Polyline> subgroupPolylines, double epsilon = 2)
        {
            // 1. 转换输入线段为Segment对象
            var allPoints = new List<PointF2G>();
            var segments = new List<Segment>();
            for(var i = 0; i < subgroupPolylines.Count; i++)
            {
                for (var j = 0; j < subgroupPolylines[i].Points.Count - 1; j++)
                {
                    segments.Add(new Segment(subgroupPolylines[i].Points[j], subgroupPolylines[i].Points[j + 1])
                    {
                        Name = i + "-" + j
                    });
                    allPoints.Add(subgroupPolylines[i].Points[j]);
                    allPoints.Add(subgroupPolylines[i].Points[j + 1]);
                }
            }

            // 2. 计算所有交点并分割线段
            var (splitSegments, intersectionPoints) = SplitSegmentsAtIntersections(segments);

            // 3. 构建带容差的图结构
            var graph = BuildGraphWithTolerance(splitSegments, epsilon);

            // 4. 追踪多边形
            var polygons = TracePolygonsWithTolerance(graph, epsilon);

            if (polygons == null || polygons.Count == 0)
            {
                return new List<Polyline>();
            }

            var rs = new List<Polyline>();
            foreach (var poly in polygons)
            {
                rs.Add(new Polyline() { Points = poly, GroupIndex = subgroupPolylines[0].GroupIndex });
            }

            return rs;
        }

        private (List<Segment>, List<PointF2G>) SplitSegmentsAtIntersections(List<Segment> segments)
        {
            var splitSegments = new List<Segment>();
            var intersectionPoints = new HashSet<PointF2G>();

            for (int i = 0; i < segments.Count; i++)
            {
                var currentSeg = segments[i];
                var splitPoints = new List<PointF2G> { currentSeg.Start, currentSeg.End };

                // 查找与当前线段的所有交点
                for (int j = 0; j < segments.Count; j++)
                {
                    if (i == j) continue;

                    var otherSeg = segments[j];

                    if(otherSeg.Start.Equals(currentSeg.Start) || otherSeg.End.Equals(currentSeg.End)
                        || otherSeg.Start.Equals(currentSeg.End) || otherSeg.End.Equals(currentSeg.Start))
                    {
                        continue;
                    }

                    var intersect = FindIntersection(currentSeg, otherSeg);

                    if (intersect != null )
                    {
                        splitPoints.Add(intersect);
                        intersectionPoints.Add(intersect);
                    }
                }

                // 按距离起点远近排序分割点
                splitPoints = splitPoints.OrderBy(p => PointFFunc.Distance(currentSeg.Start, p)).ToList();

                // 创建分割后的线段
                for (int k = 0; k < splitPoints.Count - 1; k++)
                {
                    splitSegments.Add(new Segment(splitPoints[k], splitPoints[k + 1]));
                }
            }

            return (splitSegments, intersectionPoints.ToList());
        }

        private PointF2G FindIntersection(Segment seg1, Segment seg2)
        {
            // 线段1的起点和终点
            var p1 = seg1.Start;
            var p2 = seg1.End;

            // 线段2的起点和终点
            var p3 = seg2.Start;
            var p4 = seg2.End;

            // 计算分母
            var denom = (p4.Y - p3.Y) * (p2.X - p1.X) - (p4.X - p3.X) * (p2.Y - p1.Y);

            // 如果分母为0，表示线段平行或共线
            if (Math.Abs(denom) < 1e-10)
                return null;

            // 计算ua和ub
            var ua = ((p4.X - p3.X) * (p1.Y - p3.Y) - (p4.Y - p3.Y) * (p1.X - p3.X)) / denom;
            var ub = ((p2.X - p1.X) * (p1.Y - p3.Y) - (p2.Y - p1.Y) * (p1.X - p3.X)) / denom;

            // 如果ua和ub都在0和1之间，则有交点
            if (ua >= 0 && ua <= 1 && ub >= 0 && ub <= 1)
            {
                var x = p1.X + ua * (p2.X - p1.X);
                var y = p1.Y + ua * (p2.Y - p1.Y);
                return new PointF2G(x, y);
            }

            return null;
        }

        private Dictionary<PointF2G, List<PointF2G>> BuildGraphWithTolerance(List<Segment> segments, double epsilon)
        {
            //对每个顶点控制到0.5，
            Dictionary<string, PointF2G> ks = new Dictionary<string, PointF2G>();
            for(var i = 0; i < segments.Count; i++)
            {
                var t = segments[i].Start;
                var t1 = new PointF2G((float)(Math.Round(t.X * 2.0) / 2.0f), (float)(Math.Round(t.Y * 2.0) / 2.0f));
                var key = t1.X + "-" + t1.Y;
                if(ks.ContainsKey(key))
                {
                    segments[i].Start = ks[key];
                }
                else
                {
                    segments[i].Start = t1;
                    ks.Add(key, t1);
                }

                t = segments[i].End;
                t1 = new PointF2G((float)(Math.Round(t.X * 2.0) / 2.0f), (float)(Math.Round(t.Y * 2.0) / 2.0f));
                key = t1.X + "-" + t1.Y;
                if (ks.ContainsKey(key))
                {
                    segments[i].End = ks[key];
                }
                else
                {
                    segments[i].End = t1;
                    ks.Add(key, t1);
                }
            }

            // 收集所有点
            var allPoints = segments.SelectMany(s => new[] { s.Start, s.End }).Distinct().ToList();
            for(var i = 0; i < allPoints.Count; i++)
            {
                allPoints[i].PointIndex = i;
            }

            // 构建图结构
            var graph = new Dictionary<PointF2G, List<PointF2G>>();
            foreach (var seg in segments)
            {
                var p1 = seg.Start;
                var p2 = seg.End;

                if (!graph.ContainsKey(p1)) graph[p1] = new List<PointF2G>();
                if (!graph.ContainsKey(p2)) graph[p2] = new List<PointF2G>();

                if (!graph[p1].Contains(p2)) graph[p1].Add(p2);
                if (!graph[p2].Contains(p1)) graph[p2].Add(p1);
            }

            // 添加虚拟连接（距离小于ε的点对）
            for (int i = 0; i < allPoints.Count; i++)
            {
                for (int j = i + 1; j < allPoints.Count; j++)
                {
                    var p1 = allPoints[i];
                    var p2 = allPoints[j];

                    if (PointFFunc.Distance(p1, p2) < epsilon)
                    {
                        if (!graph.ContainsKey(p1)) graph[p1] = new List<PointF2G>();
                        if (!graph.ContainsKey(p2)) graph[p2] = new List<PointF2G>();

                        if (!graph[p1].Contains(p2)) graph[p1].Add(p2);
                        if (!graph[p2].Contains(p1)) graph[p2].Add(p1);
                    }
                }
            }

            while (true)
            {
                bool hasUpdate = false;
                PointF2G removeP = null;
                foreach (var p in graph.Keys)
                {
                    if (graph[p].Count == 1)
                    {
                        graph.Remove(p);
                        removeP = p;
                        hasUpdate = true;
                        break;
                    }
                }
                if (hasUpdate == false)
                {
                    break;
                }
                foreach (var p in graph.Keys)
                {
                    for (var j = graph[p].Count - 1; j >= 0; j--)
                    {
                        if (graph[p][j].PointIndex == removeP.PointIndex)
                        {
                            graph[p].RemoveAt(j);
                        }
                    }
                }
            }
            return graph;
        }

        private List<List<PointF2G>> TracePolygonsWithTolerance(Dictionary<PointF2G, List<PointF2G>> graph, double epsilon)
        {
            var allPointPair = new List<PointF2G>();
            var pairkey = new System.Collections.Generic.HashSet<string>();
            foreach(var g in graph.Keys)
            {
                foreach(var k in graph[g])
                {
                    if(pairkey.Contains(g.PointIndex+"-"+k.PointIndex)||
                        pairkey.Contains(k.PointIndex + "-" + g.PointIndex))
                    {
                        continue;
                    }
                    pairkey.Add(g.PointIndex + "-" + k.PointIndex);
                    allPointPair.Add(g);
                    allPointPair.Add(k);
                }
            }

            var polygons = new List<List<PointF2G>>();
            var usedEdges = new HashSet<string>();

            foreach (var startPoint in graph.Keys)
            {
                foreach (var nextPoint in graph[startPoint])
                {
                    var edge = Tuple.Create(startPoint, nextPoint);
                    if (usedEdges.Contains(startPoint.PointIndex + "-" + nextPoint.PointIndex))
                    {
                        continue;
                    }
                    if (usedEdges.Contains(nextPoint.PointIndex + "-" + startPoint.PointIndex))
                    {
                        continue;
                    }
                    var polygon = new List<PointF2G>();
                    var currentPoint = startPoint;
                    var nextP = nextPoint;
                    HashSet<int> usedPointIndexs = new HashSet<int>();
                    int firstPointIndex = -1;

                    while (true)
                    {
                        if (polygon.Count > 200)
                        {
                            return null;
                        }
                        polygon.Add(currentPoint);
                        usedPointIndexs.Add(currentPoint.PointIndex);
                        if (polygon.Count == 1)
                        {
                            firstPointIndex = currentPoint.PointIndex;
                        }

                        // 获取所有可能的下一步点
                        var neighbors = graph[nextP];

                        var bestPoint=FindNextLine(currentPoint,nextP,neighbors,usedPointIndexs,firstPointIndex);
                        var bestPoint2 = FindNextLine2(currentPoint, nextP, neighbors, usedPointIndexs, firstPointIndex);
                        if (bestPoint != bestPoint2)
                        {

                        }
                        if (bestPoint == null)
                        {
                            break;
                        }


                        currentPoint = nextP;
                        nextP = bestPoint;

                        // 检查是否闭合（考虑容差）
                        if (PointFFunc.Distance(nextP, startPoint) < epsilon)
                        {
                            polygon.Add(currentPoint);
                            polygon.Add(nextP);

                            for (var k = 0; k < polygon.Count-1; k++)
                            {
                                usedEdges.Add(polygon[k].PointIndex + "-" + polygon[k + 1].PointIndex);
                            }

                            polygons.Add(polygon);
                            break;
                        }
                    }
                }
            }

            return polygons;
        }

        private PointF2G FindNextLine(PointF2G currentPoint, PointF2G nextP, List<PointF2G> neighbors, HashSet<int> usedPointIndexs,int firstPointIndex)
        {
            // 计算当前边的方向向量
            var dx = currentPoint.X - nextP.X;
            var dy = currentPoint.Y - nextP.Y;
            var th1 = Math.Atan2(dy, dx) * 180 / Math.PI;

            // 找出相对于当前边最右转的边
            int selIndex = -1;
            double degDiff = double.MaxValue;
            PointF2G bestPoint = null;
            foreach (var neighbor in neighbors)
            {
                if (usedPointIndexs.Contains(neighbor.PointIndex) && neighbor.PointIndex != firstPointIndex)
                    continue;
                if (neighbor.Equals(currentPoint))
                    continue;

                // 计算转向角度
                var ndx = neighbor.X - nextP.X;
                float ndy = neighbor.Y - nextP.Y;

                var z = dy * ndx - dx * ndy;
                var th2 = Math.Atan2(ndy, ndx) * 180 / Math.PI;
                double degDiffMe = double.MaxValue;

                if (z > 0)
                {
                    if (th1 < 0) { th1 = 360 + th1; }
                    if (th2 < 0) { th2 = 360 + th2; }
                    degDiffMe = Math.Abs(th1 - th2);
                    if (degDiffMe > 180)
                        degDiffMe = 360 - degDiffMe;
                }
                else
                {
                    if (th1 < 0) { th1 = 360 + th1; }
                    if (th2 < 0) { th2 = 360 + th2; }
                    degDiffMe = Math.Abs(th1 - th2);
                    if (degDiffMe < 180)
                        degDiffMe = 360 - degDiffMe;
                }

                if (degDiff > degDiffMe)
                {
                    degDiff=degDiffMe;
                    bestPoint = neighbor;
                }
            }
            return bestPoint;
        }

        private PointF2G FindNextLine2(PointF2G currentPoint, PointF2G nextP, List<PointF2G> neighbors, HashSet<int> usedPointIndexs, int firstPointIndex)
        {
            // 计算当前边的方向向量
            var dx = nextP.X - currentPoint.X;
            var dy = nextP.Y - currentPoint.Y;

            // 找出相对于当前边最右转的边
            var bestAngle = double.NegativeInfinity;
            PointF2G bestPoint = null;

            foreach (var neighbor in neighbors)
            {
                if (usedPointIndexs.Contains(neighbor.PointIndex) && neighbor.PointIndex != firstPointIndex)
                    continue;
                if (neighbor.Equals(currentPoint))
                    continue;

                // 计算转向角度
                var ndx = neighbor.X - nextP.X;
                var ndy = neighbor.Y - nextP.Y;
                var angle = dx * ndy - dy * ndx; // 叉积

                if (angle > bestAngle)
                {
                    bestAngle = angle;
                    bestPoint = neighbor;
                }
            }

            return bestPoint;

        }


        private void RemoveUsedSegment(List<Polyline> sourceLines, List<Polyline> usedLines)
        {
            HashSet<string> usedSegmentsStr = new HashSet<string>();
            for (var i = 0; i < usedLines.Count; i++)
            {
                for(var j = 0; j < usedLines[i].Points.Count; j++)
                {
                    var p1 = usedLines[i].Points[j].ToNearPosStr(0.5);
                    usedSegmentsStr.Add(p1);
                }
            }

            List<Polyline> newItems = new List<Polyline>();
            for (var i = sourceLines.Count - 1; i >= 0; i--)
            {
                var rs = RemoveUsedSegmentOfLine(sourceLines[i], usedSegmentsStr);
                if (rs==null)
                {
                    sourceLines.RemoveAt(i);
                }
                else
                {
                    sourceLines.RemoveAt(i);
                    newItems.AddRange(rs);
                }
            }
            for (var i = sourceLines.Count - 1; i >= 0; i--)
            {
                if (sourceLines[i].Count == 0)
                {
                    sourceLines.RemoveAt(i);
                }
            }
            sourceLines.AddRange(newItems);
        }

        private List<Polyline> RemoveUsedSegmentOfLine(Polyline polyline, HashSet<string> usedSegmentsStr)
        {
            bool[] isRemoved = new bool[polyline.Points.Count];
            int removeCount = 0;
            for (var j = polyline.Points.Count - 1; j >= 0; j--)
            {
                var p1 = polyline.Points[j].ToNearPosStr(0.5);
                if (usedSegmentsStr.Contains(p1))
                {
                    isRemoved[j] = true;
                    removeCount++;
                }
            }
            if (removeCount >= polyline.Points.Count - 1)
            {
                return null;
            }
            List<Polyline> res = new List<Polyline>();
            Polyline currentPolyline = new Polyline() { GroupIndex = polyline.GroupIndex };
            for (var i = 0; i < isRemoved.Length; i++)
            {
                if (isRemoved[i] == false)
                {
                    currentPolyline.Add(polyline.Points[i]);
                }
                else
                {
                    if (currentPolyline.Count >= 2)
                        res.Add(currentPolyline);
                    currentPolyline = new Polyline() { GroupIndex = polyline.GroupIndex };

                }
            }
            if (currentPolyline.Count >= 2)
                res.Add(currentPolyline);
            return res;
        }
    }
}
